package offer;

/**
 * <p>
 * 剑指 Offer 45. 把数组排成最小的数
 * </p>
 *
 * @author xiaozuolin
 * @date 2021/9/26 8:55
 */
public class Offer45 {

    public String minNumber(int[] nums) {
        String[] strings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strings[i] = String.valueOf(nums[i]);
        }
        quickSort(strings, 0, strings.length - 1);
        StringBuilder builder = new StringBuilder();
        for (String s : strings) {
            builder.append(s);
        }
        return builder.toString();
    }

    //快速排序
    public void quickSort(String[] strings, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l;
        int j = r;
        String tmp = strings[i];
        while (i < j) {
            while ((strings[j] + strings[l]).compareTo(strings[l] + strings[j]) >= 0 && i < j) {
                j--;
            }
            while ((strings[i] + strings[l]).compareTo(strings[l] + strings[i]) <= 0 && i < j) {
                i++;
            }
            tmp = strings[i];
            strings[i] = strings[j];
            strings[j] = tmp;
        }
        strings[i] = strings[l];
        strings[l] = tmp;
        quickSort(strings, l, i - 1);
        quickSort(strings, i + 1, r);
    }
}
